//Mon Jun  6 15:52:14 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

class AvoidRoads {
public:
	long long numWays(int, int, vector <string>);
	long long dfs(int, int, int, int, int);
	bool checkBound(int, int);
	long long grid[102][102][205];
	map<pair<pair<int, int>, pair<int, int> >, bool> badlist;
	int w;
	int h;
};

long long AvoidRoads::numWays(int width, int height, vector <string> bad) {
	w = width;
	h = height;
	memset(grid, -1, sizeof(grid));
	int x1, y1, x2, y2;
	for(int i=0; i<bad.size(); i++){
		stringstream s(bad[i]);
		s >> y1 >> x1 >> y2 >> x2;
		badlist[make_pair(make_pair(x1, y1),make_pair(x2, y2))] = true;
		badlist[make_pair(make_pair(x2, y2),make_pair(x1, y1))] = true;
	}
	return dfs(0, 0, height, width, width + height);
}

long long AvoidRoads::dfs(int cx, int cy, int ex, int ey, int moves){
	if(moves ==0) return cx==ex && cy==ey;
	long long &ret = grid[cx][cy][moves];
	if(ret != -1) return ret;
	ret = 0;
	for(int i=0; i<4; i++){
		int xx = cx + dx[i];
		int yy = cy + dy[i];
		if(checkBound(xx, yy) && !badlist[make_pair(make_pair(cx, cy), make_pair(xx, yy))]){
			ret += dfs(xx, yy, ex, ey, moves-1);
		}
	}
	return ret;
}

bool AvoidRoads::checkBound(int x, int y){
	return (x>=0 && x<=h && y>=0 && y<=w);
}

<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
